// Copyright 2008 Google Inc. All Rights Reserved.

/* Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.documents.core.treesync;

import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import com.google.documents.core.treesync.EditHandler.SourceTree;

import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * Edit script generator for TreeMerger. Generates a script of tree edits
 * reflecting the changes between the input base tree and output merged tree 
 * generated by the owning TreeMerger object. Tree edits are emitted to the
 * attached {@link EditHandler}.
 *  
 * <p>The edit script for a child list is generated by calling 
 * {@link #emitEdits}. Prior to calling this method, the caller is required to have
 * informed the generator of the origins of all update, insert, and re-ordering
 * operations in the child list. (This is done with the set*Origin methods). 
 * 
 * <p>
 * The emitted edit operations will, when executed in the emitted order,
 * transform an instance of the merger base tree to the merged tree. The edits
 * scripts is <i>well formed</i>, i.e., operations are emitted in such an order
 * that any dependent edits have already been executed. For instance, children
 * of inserted nodes are moved/added after their parent is inserted, and
 * subtrees are deleted only after any non-deleted nodes have been moved out of
 * the subtree. Another way of saying this is that no temporary subtrees 
 * detached from the main tree need to be maintained during the course of the
 * edit script.
 * 
 * <p>
 * Relevant properties of the edit script are whether they require <i>child
 * pushing</i> and if they <i>minimize the amount of moves</i>.
 * 
 * <p>
 * Child pushing means that the edit operations use target positions in the
 * child list that require intermediate nodes to be pushed towards the end of
 * the list. For instance, assume have a root node <i>r</i> with an only child
 * <i>d</i>, which will be deleted further on. Furthermore, assume we want to
 * insert <i>i</i> as the only child of <i>r</i> in the final tree. A child
 * pushing script will insert <i>i</i> at position 0, thus shifting <i>d</i>
 * towards the end (before it is finally removed), whereas a non-pushing script
 * could insert <i>i</i> at position 1 (and not until <i>d</i> is deleted will
 * <i>i</i> shift to position 0).
 * 
 * <p>
 * Minimized moves means that the amount of moves used to re-order the child
 * list to its final form is minimized. For instance, consider the initial list
 * <i>a b c d</i>, and the final list <i>b c d a</i>. One move of <i>a</i> to the end
 * of the list is sufficient to obtain the final list. However, the same result
 * is obtained e.g. with a sequence of moves that always shift the next node in
 * the final list into place <i>a b c d</i> -> <i>b a c d</i> -> <i>b c a d</i> ->
 * <i>b c d a</i>. In this case 3 moves are used.
 * 
 * <p>
 * This implementation performs child pushing and does not minimize the amount
 * of moves. Furthermore, null moves may be emitted (i.e., a move of the node
 * to the same location).
 * 
 * @author tancred (Tancred Lindholm)
 * 
 * @param <C> Node content type
 * @param <K> Node key type
 */
class EditScriptGenerator<C, K> {

  /* Implementation notes.
   * 
   * Terminology:
   *  Far move: move where the parent of the node changes
   *  Near (local) move: move where only the position in the child list changes
   * Generics:
   *  We do not use the full recursive abstract node type for clarity
   *  The full type is
   *  AbstractTreeNode<C, K, ? extends AbstractTreeNode<C, K, ?>>  
   *  
   */

  private EditHandler<? super C, ? super K> eh; // Target edit handler  
  
  private Set<K> executedFarMoves = Sets.newHashSet(); // Far moves executed

  // Set of inserted ids, who are also roots of a subtree of inserted nodes
  // We use maps rather than sets, because that way we get to store the corresponding node,
  // which we'll need anyway. 
  
  // Insert roots in tree T1
  private Map<K, AbstractTreeNode<C, K, ?>> insertRootsT1 = Maps.newHashMap();
  // Insert roots in tree T2
  private Map<K, AbstractTreeNode<C, K, ?>> insertRootsT2 = Maps.newHashMap();
  
  // Map of node id -> tree number for inserts, deletes, and moves. The tree number
  // indicates which tree originated the change to the node that is the key
  private Map<K, EditHandler.SourceTree> structChanges = Maps.newHashMap(); 
  
  // Map of node id -> tree number for updated nodes. The tree number
  // indicates which tree originated the change to the node that is the key
  private Map<K, EditHandler.SourceTree> updates = Maps.newHashMap();
  
  // See doc for DeleteTask
  private Map<K, DeleteTask<K>> delayedDeletes = Maps.newHashMap();

  // Base tree. 
  private AddressableTree<C, K, ? extends AbstractTreeNode<C, K, ?>> t0;
  // Updated trees. Used to calculate deletion/insertion roots
  private AddressableTree<C, K, ? extends AbstractTreeNode<C, K, ?>> t1; // First changed tree
  private AddressableTree<C, K, ? extends AbstractTreeNode<C, K, ?>> t2; // Second changed tree
  
  /**
   * Create a new edit script generator.
   * @param eh Edit handler that will receive tree edits
   * @param t0 merger base tree
   * @param t1 merger first edited tree
   * @param t2 merger second edited tree
   */
  public <T extends AddressableTree<C, K, ? extends AbstractTreeNode<C, K, ?>>> 
    EditScriptGenerator(EditHandler<? super C, ? super K> eh, T t0, T t1, T t2) {
    super();
    this.eh = eh;
    this.t0 = t0;
    this.t1 = t1;
    this.t2 = t2;
    computeIsInsertRoot(t1.getRoot(), insertRootsT1);
    computeIsInsertRoot(t2.getRoot(), insertRootsT2);
  }
  
  /**
   * Generate edits transforming the current child list to the merged child list. The edits,
   * i.e., the output of this method, is a series of calls to the attached edit handler.
   * 
   * <p>Note
   * that some extra nodes may still remain in the child list of the tree being
   * edited after the edits have been executed (e.g. because their final
   * destination is not yet available). However, these extra nodes will be
   * deleted/moved away once the edits for *all* child lists have been
   * generated.
   * @param parentId id of parent node
   * @param currentChildren current child list
   * @param mergedChildren merged child list
   */
  public void emitEdits(K parentId, Iterable<AbstractTreeNode<C, K, ?>> currentChildren, 
      Iterable<AbstractTreeNode<C, K, ?>> mergedChildren) {
    if (inInsertedSubtree(parentId)) {
      return; // The tree-insert edit operation for this inserted subtree has already been emitted
              // on the previous level, so nothing needs to be done.
    }
    Set<K> mergedIds = Sets.newHashSet();
    // Nodes that will still be present in the child list after we have emitted the
    // list's edits, because these ids are delayed deletes, or far moves waiting to be executed
    Set<K> phantomIds = Sets.newHashSet(); 

    K id = parentId;
    // Build list of ids in merged list. Useful for telling moves and deletes apart
    for (AbstractTreeNode<?, K, ?> cn : mergedChildren) {
      mergedIds.add(cn.getId());
    }
    //
    // ==== Handle deletes, far moves
    //
    for (AbstractTreeNode<?, K, ?> cn : currentChildren) {
      K cid = cn.getId();
      if (mergedIds.contains(cid)) {
        continue; // In merged list -> not deleted or far moved away
      } else if (isDeleted(cid)) {
        // This node is deleted; figure out the state of the whole subtree
        // First, record tree of origin based on which tree it no longer exists in
        structChanges.put(cid, !hasNode(t1, cid) ? SourceTree.FIRST : SourceTree.SECOND);
        // Create delete task
        DeleteTask<K> delTask = new DeleteTask<K>(cid, getOpSource(cid, null));
        Map<K, DeleteTask<K>> newDelayedDelTasks = computeDeleteTasks(cn, delTask);  
        if (newDelayedDelTasks.size() == 0) {
          // No dependencies, execute subtree delete task immediately
          eh.delete(cid, delTask.getSourceTree());
        } else {
          // Add delayed deletes to table
          delayedDeletes.putAll(newDelayedDelTasks);
          // These will appear as phantoms in the current list
          phantomIds.add(cid); 
        }
      } else if (!executedFarMoves.contains(cid)) {
        // Far move source case (b/c node is not deleted and not in merge list)
        // Nodes that are far-moved away from here will also still be in the merged list
        // (unless the far move is executed).
        phantomIds.add(cid);
      }
    }
    //
    // === Handle other operations
    //
    // The strategy is to compute a list where the nodes in the current and
    // merged lists are aligned, i.e.,
    // paired up, along with corresponding operations. We then execute the
    // operations.
    //
    List<AlignedNodes<C, K>> aligned = computeAlignment(currentChildren, mergedChildren,
        mergedIds, phantomIds, t0);
    SourceTree movSource = null; // Tracks previous tree originating a move
    Deque<DeleteTask<K>> deletesNoLongerDelayed = Lists.newLinkedList();
    for (AlignedNodes<C, K> a : aligned) {
      switch (a.getOperation()) {
        case NOP:
          emitNodeUpdate(a);
          break;
        case DEL:
          // The way we compute the final alignment, there should be no deletes left, so:
          throw new IllegalStateException("Deletes should be handled already");
        case INS:
          // Reached an inserted node
          AbstractTreeNode<C, K, ?> insertRoot = getInsertRoot(a.getId());
          if (insertRoot == null) {
            // No full subtree to insert, insert a single node instead
            insertRoot = new SimpleNode<C, K>(a.getContent(), a.getId()); 
          }
          eh.insert(insertRoot, id, a.getOutputPos(), getOpSource(a.getId(), null));
          break;
        case MOV_SRC:
          // Reached the source position of a move. Nothing needs to be done
          break; 
        case MOV_DST:
          // Reached the target position of a move. Move the node here.
          // Note that a single node repositioning may cause a chain of multiple moves
          // Therefore, we use the previous move source tree in case there is no
          // explicit information on the source
          // E.g. abcd -> bcda
          // The merger will not mark c as moved, but we may choose to execute this as
          // mov(b,0), ***mov(c,1)***, mov(d,2)          
          movSource = getOpSource(a.getId(), movSource);
          eh.move(a.getId(), id, a.getOutputPos(), movSource);
          if (delayedDeletes.containsKey(a.getId())) {
            // There is a delayed delete that depends on this move
            DeleteTask<K> delTask = delayedDeletes.get(a.getId());
            delTask.freeReference();
            if (!delTask.hasReference()) {
              // Last dependency moved out, schedule delete when child list complete
              // We cannot run the delete immediately, as then the output positions
              // would be shifted by one, if the delete happens to be a phantom node in this list
              deletesNoLongerDelayed.addLast(delTask);
              delayedDeletes.remove(a.getId());
            }
          } else {
            // Track executed moves that could otherwise delay future deletes
            // Note that this is mutually exclusive with a delete already having
            // a dependency on this move (a node can be only moved out of *one*
            // deleted tree), and that the node needs to be a far move
            AbstractTreeNode<C, K, ?> originalParent = t0.getNode(a.getId()).getParent();
            if (originalParent != null && !id.equals(originalParent.getId())) {
              // It is a far move, store it for book-keeping
              executedFarMoves.add(a.getId());
            }
          }
          // Finally, a moved node may also be updated.
          emitNodeUpdate(a);
          break;
        default:
          throw new IllegalStateException(); // The switch should enumerate all cases!
      }
    }
    // Emit deletes in this list that became good to go
    for (DeleteTask<K> delTask : deletesNoLongerDelayed) {
      eh.delete(delTask.getId(), delTask.getSourceTree());
    }
    updates.clear(); // We only need to keep annotations for 1 child list at a time
    structChanges.clear(); 
  }

  /**
   * Compute deletion tasks for deleted subtree. 
   * If the deleted subtree rooted at <i>n</i> can be deleted immediately
   * (contains no nodes that are in the merged tree), <code>true</code> is returned. 
   * Otherwise, any nodes that need to move out of the subtree are added 
   * to {@link #delayedDeletes}, and false is returned.
   * 
   * @see DeleteTask
   */
  protected Map<K, DeleteTask<K>> computeDeleteTasks(AbstractTreeNode<?, K, ?> n,
      EditScriptGenerator.DeleteTask<K> dt) {
    Map<K, DeleteTask<K>> taskBin = Maps.newHashMap();
    computeDeleteTasks(n, dt, taskBin);
    return taskBin;
  }
  protected boolean computeDeleteTasks(AbstractTreeNode<?, K, ?> n,
      EditScriptGenerator.DeleteTask<K> dt, Map<K, DeleteTask<K>> taskBin) {
    K id = n.getId();
    if (!isDeleted(id) && !executedFarMoves.contains(id)) {
      // This node is not deleted, and has not been moved out of this subtree
      // --> we need to enqueue it as a delayed node
      taskBin.put(id, dt);
      dt.addReference();
      return false; 
    }
    boolean childrenDeleted = true;
    for (AbstractTreeNode<?, K, ?> c : n.children()) {
      childrenDeleted &= computeDeleteTasks(c, dt, taskBin);
    }
    return childrenDeleted;
  }

  /**
   * Compute a list where the nodes in the current and merged lists are aligned, i.e.,
   * paired up. Nodes deleted or far-moved away are not present in the aligned list. 
   * This is essentially a "diff" of the current and merged lists; the alignment 
   * ideas and terminology used here is an application of string alignment algorithms and
   * concepts. To understand this code it helps a lot to know a bit about that. 
   * 
   * <p>The method works by obtaining a "raw" alignment from {@link #alignNodes}, whose
   * task is to align the nodes of the lists as "good" as possible (as few deletes and inserts
   * as possible). For instance, given the lists abcd and bcda, a "good" alignment would be
   * (using '.' on either side to mark non-aligned characters) 
   * <pre>
   * Current abcd.
   * Merged  .bcda
   * <pre>
   * 
   * where (going from current to merged) a is deleted, followed by identical runs of bcd, and
   * the a is inserted. 
   * 
   * <p>The "raw" alignment is then annotated with the operations it encodes. A pair
   * of insert and delete of the same node is a move. Since we already executed deletes,
   * there will be no delete left in the output list. Each insert and aligned node 
   * will be emitted to the final list, in the list order. We set the ouputPosition according
   * to this.
   * 
   * Returning to alignment quality, A "worse", but still valid alignment in the
   * previous case would be
   * 
   * <pre>
   * Current ...abcd
   * Merged  bcda...
   * <pre>
   * 
   * Where b, c, and d are first inserted, and then deleted. Since each delete that has
   * an insert pair corresponds to a move, it follows that we minimize moves by minimizing
   * the number of paired inserts and deletes. This is the minimum edit distance problem,
   * i.e., the raw alignment that generates the least moves is the alignment that has the
   * minimum edit distance.
   */
  protected List<AlignedNodes<C, K>> computeAlignment(Iterable<AbstractTreeNode<C, K, ?>> b,
        Iterable<AbstractTreeNode<C, K, ?>> m,
        Set<K> idsInMerged, Set<K> phantomIds,  AddressableTree<?, K, ?> tb) {
    List<AbstractTreeNode<C, K, ?>> currentInMergedList = Lists.newLinkedList();
    // Compute list of current nodes still in the merged list
    for (AbstractTreeNode<C, K, ?> nb : b) {
      if (idsInMerged.contains(nb.getId()) || phantomIds.contains(nb.getId())) {
        currentInMergedList.add(nb);
      }
    }
    // Run raw alignment algorithm
    List<AlignedNodes<C, K>> al = alignNodes(currentInMergedList, m, phantomIds);
    // Post-process output to detect moves and fill in output position
    int outputPos = 0;
    // Convert INS/DEL pairs corresponding to moves to MOV_SRC and MOV_DST
    for (AlignedNodes<C, K> a : al) {
      a.setOutputPos(a.getOperation() == 
        Op.DEL && !phantomIds.contains(a.getId()) ? -1 : outputPos++);
      if (a.getOperation() == Op.DEL 
          && (idsInMerged.contains(a.getId()) || phantomIds.contains(a.getId()))) {
        // This is from where the node is moved away
        a.setOperation(Op.MOV_SRC);
      } else if (a.getOperation() == Op.INS && hasNode(tb, a.getId())) {
        // This is where the move ends up
        a.setOperation(Op.MOV_DST);
      } else if (a.getOperation() == Op.INS) {
        // This is just a normal insert (node not in base tree), leave the operation as is
      } else if (a.getOperation() == Op.NOP) {
        // Nops need no processing
      } else {
        // Anything else (specifically, Delete) should not occur (see javadoc above)
        throw new IllegalStateException("Unexpected operation " + a);
      }
    }
    return al;
  }

  /**
   * Align nodes as well as possible. Currently, this method implements a rather dumb
   * strategy that just inserts any node that won't match the next node in the
   * original list. 
   * 
   * <p>TODO: In the future, this method should be upgraded to perform minimum
   * edit distance alignment.
   * 
   * @param base nodes in current child list that will appear in merged list
   * @param merge nodes in the merged list
   * @param phantomNodeIds set of node ids in b that are phantom nodes, i.e., nodes that
   *        are scheduled for deletion or being moved away. Can be used as a hint when
   *        generating the alignment (i.e., if the next node is a phantom, we may
   *        want to look for a matching further down the list, rather than emit an insert)
   *        
   * @return list of aligned nodes from b and m.
  */
  protected <N extends AbstractTreeNode<?, K, ?>> 
      List<AlignedNodes<C, K>> alignNodes(Iterable<AbstractTreeNode<C, K, ?>> base, 
      Iterable<AbstractTreeNode<C, K, ?>> merge,
      Set<K> phantomNodeIds) {
    List<AlignedNodes<C, K>> aligned = Lists.newArrayList(); 
    Iterator<AbstractTreeNode<C, K, ?>> baseIter = base.iterator();
    Iterator<AbstractTreeNode<C, K, ?>> mergeIter = merge.iterator();

    // Current node in base list, null values means "get next from list" (if possible)
    AbstractTreeNode<C, K, ?> nb = null; 
    // Current node in merge list, same null semantics as nb
    AbstractTreeNode<C, K, ?> nm = null; 
    while (true) {
      nb = (nb == null && baseIter.hasNext()) ? baseIter.next() : nb;
      nm = (nm == null && mergeIter.hasNext()) ? mergeIter.next() : nm;
      if (nb == null && nm == null) {
        break; // No more nodes, break out
      }
      if (nb != null && nm != null && nb.getId().equals(nm.getId())) {
        // Aligned nodes
        aligned.add(new AlignedNodes<C, K>(nb.getId(), Op.NOP, nm.getContent()));
        // Get next from both lists
        nb = null;
        nm = null;
      } else if (nb != null && phantomNodeIds.contains(nb.getId())) {
        aligned.add(new AlignedNodes<C, K>(nb.getId(), Op.DEL, null)); // Deleted from nb list
        nb = null;
      } else if (nm != null) {
        // Arbitrarily emit an insert (this is the dumb alignment phase)
        aligned.add(new AlignedNodes<C, K>(nm.getId(), Op.INS, nm.getContent()));
        // Try with the next node from the merged list
        nm = null;
      } else if (nm == null) {
        aligned.add(new AlignedNodes<C, K>(nb.getId(), Op.DEL, null));
        // Try with the next node from the current list
        nb = null;
      } else {
        throw new IllegalStateException("Bad state -- both lists exhausted");
      }
    }
    return aligned;
  }

  /**
   * Emit any update associated with this node.
   */
  protected void emitNodeUpdate(AlignedNodes<C, K> a) {
    if (updates.containsKey(a.getId())) {
      eh.update(a.getContent(), a.getId(), updates.get(a.getId()));            
    }
  }

  /**
   * Obtain source tree of structure-changing operation. The method will fail
   * if there is no source tabulated in {@link #structChanges}, and no default source.
   * (In this case the merging algorithm has not fulfilled its contract.)
   * 
   * @param id node that has been inserted/deleted/moved. 
   * @param defaultSource source to use if none is tabulated.
   * @return source tree
   */
  private SourceTree getOpSource(K id, SourceTree defaultSource) {
    SourceTree sourceTree = structChanges.get(id);    
    if (sourceTree == null) {
      if (defaultSource != null) {
        sourceTree = defaultSource;
      } else {
        throw new IllegalStateException("Merger did not give source tree for operation");
      }
    }
    return sourceTree;
  }

  /**
   * Inform script generator of origin of insert.
   * 
   * @param n inserted node
   * @param tree tree of origin
   */
  public void setInsertOrigin(AbstractTreeNode<C, K, ?> n, SourceTree tree) {
    structChanges.put(n.getId(), tree);
  }

  /**
   * Inform script generator of origin of update.
   * 
   * @param n inserted node
   * @param tree tree of origin
   */
  public void setUpdateOrigin(AbstractTreeNode<C, K, ?> n, SourceTree tree) {
    updates.put(n.getId(), tree);
  }

  /**
   * Inform script generator of origin of node re-ordering.
   * 
   * @param n inserted node
   * @param tree tree of origin
   */
  public void setReorderOrigin(AbstractTreeNode<C, K, ?> n, SourceTree tree) {
    structChanges.put(n.getId(), tree);
  }

  /**
   * Determine if node is deleted.
   * 
   * @param id id of node to check
   * @return <code>true</code> if node is deleted
   */
  private boolean isDeleted(K id) {
    return !(hasNode(t1, id) && hasNode(t2, id));
  }

  /**
   * Get root node of inserted subtree.
   *  
   * @param id id of node
   * @return root node from T1 or T2 of inserted subtree, or <code>null</code> if id does not
   *    identify a root node of an inserted subtree.
   */
  private AbstractTreeNode<C, K, ?> getInsertRoot(K id) {
    AbstractTreeNode<C, K, ?> insRoot = insertRootsT1.get(id);
    if (insRoot == null) {
      insRoot = insertRootsT2.get(id);
    }
    return insRoot;
  }

  /**
   * Test if a node is in an inserted subtree. The root of an inserted subtree
   * is considered in the inserted subtree.
   * 
   * @param id id of node in T1 or T2
   * @return true if node is in inserted subtree
   */
  private boolean inInsertedSubtree(K id) {
    return inInsertedSubtree(t1.getNode(id), insertRootsT1)
        || inInsertedSubtree(t2.getNode(id), insertRootsT2);
  }

  /**
   * Test if a node is in an inserted subtree. The root of an inserted subtree
   * is considered in the inserted subtree.
   * 
   * @param n node to test
   * @param insertRoots set of insertion roots for the tree that n is in
   * @return true if node is in inserted subtree 
   */
  private boolean inInsertedSubtree(
      AbstractTreeNode<C, K, ?> n, Map<K, AbstractTreeNode<C, K, ?>> insertRoots) {
    if (n == null) {
      // The null node (parent of the root) is never in an inserted subtree
      return false;
    } else if (insertRoots.containsKey(n.getId())) {
      // Trivially true
      return true; 
    } else {
      // in inserted subtree if any ancestor is in inserted subtree      
      return inInsertedSubtree(n.getParent(), insertRoots); 
    }
  }

  /**
   * Compute insertion root status for nodes in a subtree.
   *   
   * @param n root node of subtree to compute insertion status for 
   * @param roots map to which <m.id,m> is added for all nodes m in the
   *    subtree of n that are insertion roots
   * @return true if <i>n</i> is the root of an inserted subtree
   */
  private boolean computeIsInsertRoot(AbstractTreeNode<C, K, ?> n, 
      Map<K, AbstractTreeNode<C, K, ?>> roots) {
    K id = n.getId();
    // NOTE: Same id-inserts in both trees are not eligible for subtree-inserts,
    // (they need to be inspected individually by the merge algorithm)
    // which is why we define isInserted to allow an id in only one tree ->
    // XOR rather than OR in the test below
    boolean isInserted = !hasNode(t0, id) && (hasNode(t1, id) ^ hasNode(t2, id));
    for (AbstractTreeNode<C, K, ?> child : n.children()) {
      isInserted &= computeIsInsertRoot(child, roots);
    }
    if (isInserted) {
      // This node, and all its children (recursively) are inserted ->
      // This node is an insertion root.
      roots.put(id, n);
      // The recursive steps will have marked the children as insertion roots,
      // undo that 
      for (AbstractTreeNode<?, K, ?> cn : n.children()) {
        roots.remove(cn.getId());
      }      
    }    
    return isInserted;
  }

  private final boolean hasNode(AddressableTree<?, K, ?> t, K id) {
    return t.getNode(id) != null;
  }
  
  /** 
   * A delayed subtree delete. A delayed delete depends on a set of nodes N that needs
   * to be moved out of the subtree before the delete may execute. In this 
   * implementation, the nodes in N are stored as keys in {@link #delayedDeletes}, with
   * the corresponding (same) delete task as value. Whenever a move of a node m
   * is executed any entry for that node's id is removed from the map. A reference counting 
   * mechanism is used to count the number of entries for each task still in the map, and
   * when the last entry is removed the deletion task is executed.
   */
  private static class DeleteTask<K> {
    private K id;
    int refCounter = 0;
    SourceTree sourceTree;
    
    /**
     * Create new task.
     * @param id id of subtree to delete
     * @param sourceTree tree originating the delete
     */
    public DeleteTask(K id, SourceTree sourceTree) {
      this.id = id;
      this.sourceTree = sourceTree;
    }

    /**
     * Increment use count.
     */
    public void addReference() {
      refCounter++;
    }
    
    /**
     * Decrement use count.
     */
    public void freeReference() {
      refCounter--;
    }

    /**
     * Check if use count is zero.
     * @return <code>true</code> if the use count reached zero.
     */
    public boolean hasReference() {
      return refCounter != 0;
    }
    
    
    /**
     * Get id of subtree to deleted.
     * @return id
     */
    public K getId() {
      return id;
    }

    /**
     * Get tree originating delete.
     * @return tree originating delete
     */
    public SourceTree getSourceTree() {
      return sourceTree;
    }
    
  }

  /** 
   * Internally used set of structure operations on nodes.
   */
  enum Op {NOP, INS, DEL, MOV_SRC, MOV_DST}

  /**
   * A pair of aligned nodes, along with annotations used to generate the edit script.
   * The annotations are: position in final child list, operation associated with the
   * node, and the final content of the node.
   */
  static class AlignedNodes<C, K> {
    private K id;
    private int outputPos;
    private Op operation;
    private C content;
    
    public AlignedNodes(K id, Op operation, C content) {
      this.id = id;
      this.operation = operation;
      this.content = content;
    }

    public K getId() {
      return id;
    }

    public void setOutputPos(int outputPos) {
      this.outputPos = outputPos;
    }

    public int getOutputPos() {
      return outputPos;
    }

    public void setOperation(Op operation) {
      this.operation = operation;
    }

    public Op getOperation() {
      return operation;
    }

    public C getContent() {
      return content;
    }
  }
}
